import java.util.Arrays;

public class sort {

    public static void main(String[] args) {
        int[] nums = new int[]{10,2,4,5,15,17,89,656,422,9009};
        sort sort =new sort();
        sort.quickSort(nums);
        System.out.println(Arrays.toString(nums));
    }

    public void quickSort(int[] nums){
        helper(nums,0,nums.length-1);
    }

    public void helper(int[] nums,int left,int right){
        if (left > right)
            return;
        int base = nums[left];
        int i = left, j = right;
        while (i != j) {
            while (nums[j] >= base && i < j)
                j--;
            while (nums[i] <= base && i < j)
                i++;
            if (i < j)
                swap(nums, i, j);
        }
        swap(nums, left, i);
        helper(nums, left, i - 1);
        helper(nums, i + 1, right);
    }

    private void swap(int[] nums, int i, int j) {
        int tmp = nums[i];
        nums[i] = nums[j];
        nums[j] = tmp;
    }
}
